/**
 * 并查集，下面这些实现是最基本的功能
 * 并没有优化结构
 */

#include<stdio.h>
#include<stdlib.h>


#define SIZE 100

//集合元素数组，数组元素的值是父节点的下标。
//之前的顺序结构树，元素值是左右子树的下标
int dsu[SIZE];
/**
 * 将集合s中的每个元素初始化为只有一个单元素的子集合
 * -1表示没有连接到其他节点，即子树为空
 */
void dsu_init(int s[]){
    for(int i=0;i<SIZE;i++){
        s[i]=-1;
    }
}


/**
 * 将集合s中的子集合roo2并入root1，要求root1 root2互不相交，否则不合并
 * 下面这个函数可以改进，让两个子树连接后的树层数更小，方法就是将小树合并到大树
 */

void dsu_union(int s[],int root1,int root2){
    if(root1==root2) return;
    s[root2]=root1;//将根root2连接到另一个根root1下面
}

/// @brief 下面的代码是错误的！！！合并之前先判断两个集合的元素数量，将小树合并到大树
/// @param s 
/// @param root1 
/// @param root2 
void optimized_dsu_union(int s[],int root1,int root2){
    if(root1==root2){
        return ;
    }
    //下面的代码是书上的，这里判断方法是不是不合适？
    //s[root2]里面保存的一个root2的根，和元素个数有什么关系?
    //还是说将-1的那个值变成了元素个数？应该不是
    if(s[root2]>s[root1]){//如果root2里面的
        s[root1]+=s[root2];//累加集合元素个数到大树上面
        s[root2]=root1;//将小树连接到大树
    }else{
        s[root2]+=s[root1];
        s[root1]=root2;
    }
}

/**
 * 查找集合s中的元素x所在的集合，并返回s的根节点
 */
int dsu_find(int s[], int x){
    while (s[x]>=0)//循环找根
    {
        x=s[x];
    }
    return x;
}

/// @brief 在查找的过程中压缩路径，如果我们最后找到的a的根为r，那么要想办法将a直接连到r上，也就是dsu[a]=r
/// @param s 并查集
/// @param x 查找x的根
/// @return 
int optimized_dsu_find(int s[],int x){
    int root=x;
    while(s[root]>=0){
        root=s[root];
    }
    while(x!=root){
        int t=s[x];
        s[x]=root;//这一步是关键，将x的根直接置为root
        x=t;
    }
    return root;
}